<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var solveSudoku = function (board) {
        function backTracking(board) {
          //二维递归确定棋子位置
          for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
              if (board[i][j] != '.') continue

              //9个元素判断是否符合条件,这也就是为什么不需要终止条件，因为9个元素都要试一遍，不成功直接return false即可
              for (let k = 1; k <= 9; k++) {
                if (isValid(i, j, `${k}`, board)) {
                  board[i][j] = `${k}`
                  //因为只需要判断有没有棋盘满足条件，所以遍历一条边
                  if (backTracking(board)) {
                    return true
                  }
                  //回溯
                  board[i][j] = '.'
                }
              }
              //9个数都不满足，那么直接return false
              return false
            }
          }
          //如果中途没有return false，说明真的找到了那个棋盘
          return true
        }
        function isValid(row, col, val) {
          //判断一列里是否有重复
          for (let i = 0; i < 9; i++) {
            if (board[i][col] == val) {
              return false
            }
          }
          //判断一行里是否有重复
          for (let j = 0; j < 9; j++) {
            if (board[row][j] == val) {
              return false
            }
          }
          //判断小方格里是否重复
          //获取小方格左上角的起始坐标
          let startRow = Math.floor(row / 3) * 3
          let startCol = Math.floor(col / 3) * 3
          for (let i = startRow; i < startRow + 3; i++) {
            for (let j = startCol; j < startCol + 3; j++) {
              if (board[i][j] == val) {
                return false
              }
            }
          }
          return true
        }
        backTracking(board)
        return board
      }
    </script>
  </body>
</html>
